//
// Created by 16933 on 2022/11/21.
//

#include "Algorithm_Floyd.h"
#include <stdio.h>

/**
 * @brief 算法初始化函数
 * */
void Floyd_Init(FloydControler* controler, SystemControler* system_data)
{
    controler->mgraph = system_data->graph_data;
    controler->start_point = system_data->start_point;
    controler->end_point = system_data->end_point;
    controler->route[0] = controler->start_point;
    controler->route_num = 1;
    /* 初始化两张表 */
    for (int i = 0; i < MAX_VERTICES-1; ++i) {
        for (int j = 0; j < MAX_VERTICES-1; ++j) {

            controler->relay_node_table[i+1][j+1] = GIGANTIC;
            if (controler->mgraph->arc[i+1][j+1] == 0)
            {
                if (i == j)
                {
                    controler->shortest_distance_table[i+1][j+1] = 0;
                } else
                {
                    controler->shortest_distance_table[i+1][j+1] = GIGANTIC;
                }

            }
            else
            {
                controler->shortest_distance_table[i+1][j+1] = controler->mgraph->arc[i+1][j+1];
            }
        }

    }
}

/**
 * @brief 算法控制器释放
 * */
 void Floyd_Relese(FloydControler* controler)
{
     controler->route_num = 0;
     controler->start_point = 0;
     controler->end_point = 0;
     controler->sum_distance = 0;
}



/**
 * @brief 更新循环
 * */
 void Floyd_Upgrade_Loop(FloydControler* controler)
{
     int node_num = controler->mgraph->numNodes;
     //最短距离表更新
    for (int v = 1; v < node_num; ++v) {
        for (int i = 1; i < node_num+1; ++i) {
            for (int j = 1; j < node_num+1; ++j) {
                //中继节点到某一点不通就不更新
                if (controler->shortest_distance_table[i][v]==GIGANTIC || controler->shortest_distance_table[v][j] == GIGANTIC)
                {
                    ;
                }
                else
                {   //中继到两边都通，总长更小就更新
                    if ((controler->shortest_distance_table[i][j] == GIGANTIC) || (controler->shortest_distance_table[i][j]>controler->shortest_distance_table[i][v]+controler->shortest_distance_table[v][j]))
                    {
                        controler->shortest_distance_table[i][j] = controler->shortest_distance_table[i][v]+controler->shortest_distance_table[v][j];
                        controler->relay_node_table[i][j] = v;      //更新中继节点表
                    }
                }

            }
        }

    }

}


/**
 * @brief 寻找最短路径
 * */

void Floyd_Find_Path(FloydControler* controler,int start,int end)
{
    if (controler->relay_node_table[start][end] == GIGANTIC)
    {
        controler->route[controler->route_num++] = end;
        controler->sum_distance+=controler->shortest_distance_table[start][end];

    } else
    {
        int mid = controler->relay_node_table[start][end];
        Floyd_Find_Path(controler,start,mid);
        Floyd_Find_Path(controler,mid,end);
    }
}